부산대학교자료구조
Scientific Inference Lab

Keys to Indices

Hash Tables

해시테이블(hash table)은 해시 함수로 키에서 배열 인덱스를 계산해 Map 연산을 수행한다. 앞에서부터 차례로 찾는 대신 계산한 위치의 버킷만 확인하므로, 키가 고르게 퍼지면 기대 비용이 O(1)에 가깝다.

Map ADTset(k, v), get(k), contains(k), remove(k)로 키와 값을 다룬다.
해시테이블의 세 부분해시 함수, 버킷 배열, 충돌 처리가 함께 있어야 한다.
O(1)의 조건해시 계산이 빠르고 키가 고르게 퍼지며 표가 충분히 커야 한다.

순차 탐색은 최악에 n개를 보지만 해시테이블은 계산한 버킷만 본다

찾을 키를 바꾸면 리스트에서 앞부터 비교하는 횟수와, h(k) = k mod 11로 고른 버킷에서 비교하는 횟수가 바뀐다.

위 줄은 앞에서부터 비교하는 리스트, 아래 줄은 길이 11인 버킷 배열이다. 파란 칸은 비교한 원소, 초록 테두리 칸은 찾은 원소 또는 계산한 버킷이다.

Map은 정수 위치가 아니라 키로 값을 저장하고 찾는다

단계를 옮기면 dict 연산 하나가 실행되고, 저장된 키와 값 쌍, 반환값이 바뀐다.

    왼쪽은 연산 순서이고 짙은 줄이 방금 실행한 연산이다. 오른쪽 표는 지금 저장된 키와 값이며 초록 칸이 방금 바뀐 쌍이다.